﻿// 力扣：91. 解码方法
// 链接：https://leetcode.cn/problems/decode-ways/description/


// 方法：动态规划（Dynamic Programming, DP）

// 法一：
class Solution
{
public:
    int numDecodings(string s)
    {
        int n = s.size();                               // 获取字符串的长度

        vector<int> dp(n);                              // 动态规划数组，记录到第 i 个字符的解码方式数
        dp[0] = s[0] != '0';                            // 如果第一个字符不是 '0'，则可以解码，dp[0] = 1；否则 dp[0] = 0

        if (n == 1)
        {
            return dp[0];                               // 如果只有一个字符，直接返回结果
        }

        if (s[0] != '0' && s[1] != '0')
        {
            dp[1] += 1;                                 // 如果前两个字符都不为 '0'，则第二个字符也有解码方式
        }

        int temp = (s[0] - '0') * 10 + s[1] - '0';      // 计算前两个字符构成的数字

        if (temp >= 10 && temp <= 26)
        {
            dp[1] += 1;                                 // 如果这个数字在 10 到 26 之间，也可以解码成一个字母（这样就能避免前导零 01 这种情况）
        }

        // 从第三个字符开始，进行动态规划更新
        for (int i = 2; i < n; i++)
        {
            if (s[i] != '0')
            {
                dp[i] += dp[i - 1];                     // 如果当前字符不是 '0'，则可以作为一个单独字符解码
            }

            int temp = (s[i - 1] - '0') * 10 + s[i] - '0';// 计算当前字符和前一个字符组成的数字

            if (temp >= 10 && temp <= 26)
            {
                dp[i] += dp[i - 2];                     // 如果这个数字在 10 到 26 之间，也可以作为两字符解码
            }
        }

        return dp[n - 1];                               // 返回最后一个字符的解码方式数
    }
};


// 法二：
class Solution
{
public:
    int numDecodings(string s)
    {
        int n = s.size();

        if (s[0] == '0')
        {
            return 0;                                   // 如果字符串以 '0' 开头，无法解码，因为单个 '0' 无法解码成任何字母
        }

        vector<int> dp(n + 1, 0);                       // dp[i] 表示前 i 个字符的解码方式数

        // 初始化
        dp[0] = 1;                                      // 空字符串有一种解码方式，表示从没有字符开始是有效的解码方式
        dp[1] = 1;                                      // 第一个字符有一种解码方式（前提是它不为 '0'，否则会被处理掉，已经在上面处理过了）

        // 从第二个字符开始，进行递推计算解码方式数
        for (int i = 2; i <= n; i++)
        {
            // 1. 当前字符单独解码的情况
            if (s[i - 1] != '0')  
            {
                dp[i] += dp[i - 1];                     // 如果当前字符不是 '0'，即当前字符可以解码成一个字母，解码方式数继承前一个状态
            }

            // 2. 当前和前一个字符组成两位数解码的情况
            int twoDigit = (s[i - 2] - '0') * 10 + (s[i - 1] - '0');
            // 如果两位数字在 [10, 26] 之间，说明是有效的解码方式（例如：'12' -> 'L'）
            if (twoDigit >= 10 && twoDigit <= 26)
            {
                dp[i] += dp[i - 2];                     // 当前两位数可以解码成一个字母，解码方式数继承前两个状态
            }

            // 3. 如果当前字符是 '0' 且无法组成有效的两位数（即 '10' 到 '26' 之外）
            if (s[i - 1] == '0' && (twoDigit < 10 || twoDigit > 26))
            {
                return 0;                               // 此时我们不能继续解码，返回 0
            }
        }

        return dp[n];                                   // 最终的解码方式数是前 n 个字符的解码方式数
    }
};
